import pprint


class Ab():
    def numIslands(self, grid):
        if not grid:
            return 0

        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                # print(grid[i][j])
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    count += 1
                    print(count)
        return count

    def dfs(self, grid, i, j):
        # 不等于1就返回
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1':
            return

                # if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == '0': 这个是错的
                # (0,0)变成 # 后到(1,0)变成#  到(2,0)遇到0返回,到(0,0)变成# 再到(1,0) 会一直循环
                # 应该是只要不为1就return  不为1 包括为0和为# 两种情况   =='0' 漏了=='#'

        # 等于1就变成#号
        grid[i][j] = '#'
        pprint.pprint(grid)
        print()
        self.dfs(grid, i + 1, j)  # 下
        self.dfs(grid, i - 1, j)  # 上
        self.dfs(grid, i, j + 1)  # 右
        self.dfs(grid, i, j - 1)  # 左


a = Ab()
grid = [["1", "1", "0", "0", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "1", "0", "0"],
        ["0", "0", "0", "1", "1"]]

# print(type(grid[2][2]))  str
print(a.numIslands(grid))

# grid = [[1, 1, 0, 0, 0],
#       [1, 1, 0, 0, 0],
#      [0, 0, 1, 0, 0],
#      [0, 0, 0, 1, 1]]   int
